Post-rebuttal: The authors have promised to incorporate an exposition of the sampler in the revised paper, I believe that will make the paper a more self-contained read. I maintain my rating of strong accept (8). I think this paper makes very nice contributions to the fundamental question of estimating the MLE distribution given a bunch of observations. I think the key contributions can be broken up into two key parts: - A bunch of simple but elegant structural results for the MLE distribution in terms of'tent distributions' -- distributions such that its log-density is piecewise linear, and is supported over subdivisions of the convex hull of the datapoints. This allows them to write a convex program for optimizing over tent distributions.

The submission provides a polynomial-time approximation algorithm for finding the maximum-likelihood log-concave density for a given set of data points in R d, for arbitrary d. The work is theoretical in nature, with proofs and no experiments. The problem is very interesting, since log-concave distributions include may of the commonly used parametric families (such as Gaussian), and the log-concave MLE has also other interesting properties. Previously the sample-complexity of learning a log-concave distribution has been studied, but a polynomial-time algorithm has been lacking. The present work provides such an algorithm.

We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given n points in \mathbb{R} d and an accuracy parameter \eps 0, runs in time \poly(n,d,1/\eps), and returns a log-concave distribution which, with high probability, has the property that the likelihood of the n points under the returned distribution is at most an additive \eps less than the maximum likelihood that could be achieved via any log-concave distribution. This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task. Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, locally'' possesses key properties of exponential families. This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method. Efficiently approximating the (sub) gradients of the objective function of this optimization problem is quite delicate, and is the main technical challenge in this work.

We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given $n$ points in $\mathbb{R} d$ and an accuracy parameter $\eps 0$, runs in time $\poly(n,d,1/\eps),$ and returns a log-concave distribution which, with high probability, has the property that the likelihood of the $n$ points under the returned distribution is at most an additive $\eps$ less than the maximum likelihood that could be achieved via any log-concave distribution. This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task. Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, locally'' possesses key properties of exponential families. This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method.